package com.zjsru.plan2023.oneday;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: cookLee
 * @Date: 2023-09-11
 * 课程表 III
 */
public class ScheduleCourse {
    /**
     * 输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
     * 输出：3
     * 解释：
     * 这里一共有 4 门课程，但是你最多可以修 3 门：
     * 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
     * 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
     * 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
     * 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
     * \
     * 输入：courses = [[1,2]]
     * 输出：1
     */
    public static void main(String[] args) {
        ScheduleCourse scheduleCourse = new ScheduleCourse();
        int[][] courses = new int[][]{{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}};
        System.out.println(scheduleCourse.scheduleCourse(courses));
    }

    /**
     * 课程
     * @param courses
     * @return int
     */
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);

        PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
        // 优先队列中所有课程的总时间
        int total = 0;

        for (int[] course : courses) {
            int curr = course[0];
            int  deadTime = course[1];
            if(total + curr <= deadTime){
                total += curr;
                q.offer(curr);
            } else if (!q.isEmpty() && q.peek() > curr) {
                //如果当前优先队列中所有课程的总时间之和大于 dead time,那么我们找到优先队列中的最大元素exist,如果exist>curr 则移出优先队列，并且把curr加入
                Integer exist = q.poll();
                total -= exist - curr;
                q.offer(curr);
            }
        }

        return q.size();
    }
}
